package com.caoyanan.algorithm.question.zuoTraining.training003.class07;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 一条直线最多穿过点数
 *
 * 给定两个数组arrx和arry，长度都为N。代表二维平面上有N个点，
 * 第i个点的x 坐标和y坐标分别为arrx[i]和arry[i]，返回求一条直线最多能穿过多少个点?
 * @author: caoyanan
 * @time: 2021/5/24 2:18 下午
 */
public class Question07_LineCrossPointCount {

    public static void main(String[] args) {
        //(4, 1) (7, 4) (8, 5)
        int answer2 = mostPoints(new int[]{4, 7, 8}, new int[]{1, 4, 5});
        System.out.println("(4, 1) (7, 4) (8, 5)是" + answer2);
        //(6, 2) (6, 6) (1, 6)是3，错误
        int answer1 = mostPoints(new int[]{6, 6, 1}, new int[]{2, 6, 6});
        System.out.println("(6, 2) (6, 6) (1, 6)是" + answer1);
        int count = 1000;
        for (int i = 0; i < count; i++) {
            int pointCount = 3;
            int[] arrx = LogarithmInputGenerator.getInstance().generateRandomArray(pointCount, 8);
            int[] arry = LogarithmInputGenerator.getInstance().generateRandomArray(pointCount, 8);
            for (int j = 0; j < pointCount; j++) {
                System.out.printf("(%s, %s) ", arrx[j], arry[j]);
            }
            int maxCount = mostPoints(arrx, arry);
            System.out.println("答案是:" + maxCount);
        }
    }

    /**
     * 一条直线穿过的最多点数
     * 遍历每个点，求必须传过这个点的直线最多经过多少个点
     *  四种情况，一是和这个点重合，一是sameY斜率是0，一是sameX斜率无穷大，一是斜率大于0小于无穷大
     * @param arrx
     * @param arry
     * @return
     */
    private static int mostPoints(int[] arrx, int[] arry) {
        if (arrx.length == 0 || arrx.length != arry.length) {
            return 0;
        }

        int maxCount = 1;
        for (int i = 0; i < arrx.length; i++) {
            int sameX = 0;
            int sameY = 0;
            int coincide = 1;
            Map<Integer, Map<Integer, Integer>> slope = new HashMap<>();
            for (int j = i + 1; j < arrx.length; j++) {
                //比较第i个点和第j个点，即 (arrx[i], arry[i]) 和 (arrx[j], arry[j])两个点
                if (arrx[i] == arrx[j] && arry[i] == arry[j]) {
                    coincide++;
                } else if (arrx[i] == arrx[j]) {
                    sameX ++;
                } else if (arry[i] == arry[j]) {
                    sameY ++;
                } else {
                    int molecular = arrx[i] - arrx[j];
                    int denominator = arry[i] - arry[j];
                    int gcd = gcd(molecular, denominator);
                    molecular /= gcd;
                    denominator /= gcd;
                    Map<Integer, Integer> molecularMap = slope.computeIfAbsent(molecular, k -> new HashMap<>());
                    molecularMap.put(denominator, molecularMap.computeIfAbsent(denominator, k -> 0) + 1);
                }

                Integer slopeMax = slope.values().stream().flatMap(it -> it.values().stream())
                        .max(Integer::compareTo).orElse(0);

                maxCount = Math.max(maxCount, Math.max(Math.max(sameX, sameY), slopeMax) + coincide);
            }
        }
        return maxCount;
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
